{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Permutation Sequence"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #recursion #math"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #递归 #数学"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: getPermutation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #排列序列"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给出集合 <code>[1,2,3,...,n]</code>，其所有元素共有 <code>n!</code> 种排列。</p>\n",
    "\n",
    "<p>按大小顺序列出所有排列情况，并一一标记，当 <code>n = 3</code> 时, 所有排列如下：</p>\n",
    "\n",
    "<ol>\n",
    "\t<li><code>\"123\"</code></li>\n",
    "\t<li><code>\"132\"</code></li>\n",
    "\t<li><code>\"213\"</code></li>\n",
    "\t<li><code>\"231\"</code></li>\n",
    "\t<li><code>\"312\"</code></li>\n",
    "\t<li><code>\"321\"</code></li>\n",
    "</ol>\n",
    "\n",
    "<p>给定 <code>n</code> 和 <code>k</code>，返回第 <code>k</code> 个排列。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 3, k = 3\n",
    "<strong>输出：</strong>\"213\"\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 4, k = 9\n",
    "<strong>输出：</strong>\"2314\"\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 3, k = 1\n",
    "<strong>输出：</strong>\"123\"\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 <= n <= 9</code></li>\n",
    "\t<li><code>1 <= k <= n!</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [permutation-sequence](https://leetcode.cn/problems/permutation-sequence/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [permutation-sequence](https://leetcode.cn/problems/permutation-sequence/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['3\\n3', '4\\n9', '3\\n1']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getPermutation(self, n: int, k: int) -> str:\n",
    "        res = []\n",
    "        k = k - 1\n",
    "        candidates = [i + 1 for i in range(n)]\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            fac = math.factorial(i)\n",
    "            order = k // fac\n",
    "            k = k - order * fac\n",
    "            res.append(str(candidates.pop(order)))\n",
    "        \n",
    "        return ''.join(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getPermutation(self, n: 'int', k: 'int') -> 'str':\n",
    "        f = list(range(0, n + 1))\n",
    "        f[0] = 1\n",
    "        for i in range(2, n + 1):\n",
    "            f[i] *= f[i - 1]\n",
    "\n",
    "        cand = list(range(1, n + 1))\n",
    "        l = n - 1\n",
    "        ret = ''\n",
    "        while k and cand:\n",
    "            i = 0\n",
    "            while k > f[l]:\n",
    "                i += 1\n",
    "                k -= f[l]\n",
    "            ret += str(cand[i])\n",
    "            l -= 1\n",
    "            cand.pop(i)\n",
    "        # print(ret)\n",
    "        return ret\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getPermutation(self, n, k):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :type k: int\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        temp_data = []\n",
    "        temp_value = 1\n",
    "        for i in range(1, n + 1):\n",
    "            temp_data.append(i)\n",
    "            temp_value *= i\n",
    "        k -= 1\n",
    "        result = []\n",
    "        for i in range(n):\n",
    "            temp_value /= (n - i)\n",
    "            selected = int(k / temp_value)\n",
    "            result.append(str(temp_data[selected]))\n",
    "            for j in range(selected, n - i - 1):\n",
    "                temp_data[j] = temp_data[j + 1]\n",
    "            k = k % temp_value\n",
    "        return \"\".join(result)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getPermutation(self, n, k):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :type k: int\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        factorials = [1]*(n+1)\n",
    "        for i in range(1, n+1):\n",
    "            factorials[i] = factorials[i-1]*i\n",
    "            \n",
    "        n_list = [i for i in range(1, n+1)]\n",
    "\n",
    "        k -= 1\n",
    "        res = ''\n",
    "        for i in range(1, n+1):\n",
    "            m = k // factorials[n-i]\n",
    "            k %= factorials[n-i]     \n",
    "            res += str(n_list[m])\n",
    "            n_list.remove(n_list[m])\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getPermutation(self, n, k):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :type k: int\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        res = []\n",
    "        charOfChoice = [str(char) for char in range(1, n+1)]    # 表示可供选择的字符\n",
    "        import functools\n",
    "        import math\n",
    "        for i in range(n, 0, -1):\n",
    "            totalOfPermutation = functools.reduce(lambda x,y : x*y, range(1, i+1))\n",
    "            index = math.ceil(k*i/totalOfPermutation)\n",
    "            res += charOfChoice[index-1]\n",
    "            charOfChoice = charOfChoice[:index-1] + charOfChoice[index:]\n",
    "            k = k - (index-1) *totalOfPermutation/i\n",
    "            if k <= 0:\n",
    "                res += charOfChoice\n",
    "                return ''.join(res)\n",
    "        return ''.join(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getPermutation(self, n: int, k: int) -> str:\n",
    "        res = []\n",
    "        pos = n\n",
    "        path = [i for i in range(1,n+1)]\n",
    "        while k > 0:\n",
    "            pos -= 1\n",
    "            cur = math.factorial(pos)\n",
    "            if cur > k:\n",
    "                res.append(path[0])\n",
    "                path.remove(path[0])\n",
    "            elif k % cur == 0:\n",
    "                digit = k // cur\n",
    "                res.append(path[digit-1])\n",
    "                path.remove(path[digit-1])\n",
    "                path.reverse()\n",
    "                for i in path:  # 792346851\n",
    "                    res.append(i)\n",
    "                break\n",
    "            else:\n",
    "                digit = k //cur\n",
    "                res.append(path[digit])\n",
    "                path.remove(path[digit])\n",
    "                pre = k//cur * cur\n",
    "                k -= pre\n",
    "        str_list = \"\".join([str(i) for i in res])\n",
    "        return str_list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getPermutation(self, n: int, k: int) -> str:\n",
    "        allFactorial = [1, 1]\n",
    "        for i in range(2, n + 1):\n",
    "            allFactorial.append(allFactorial[-1] * i)\n",
    "        s, k, res = list(range(1, n + 1)), k - 1, \"\"\n",
    "        for i in range(len(s) - 1, -1, -1):\n",
    "            res += str(s[k // allFactorial[i]])\n",
    "            print(s)\n",
    "            del s[k // allFactorial[i]]\n",
    "            k %= allFactorial[i]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getPermutation(self, n: int, k: int) -> str:\n",
    "        sta = [0,1]\n",
    "        ans = []\n",
    "        nums = [i for i in range(n+1)]\n",
    "        for i in range(2,n+1):\n",
    "            sta.append(i*sta[-1])\n",
    "        while n>1:\n",
    "            if k%sta[n-1]==0: \n",
    "                i =k//sta[n-1]\n",
    "            else: i = k//sta[n-1]+1\n",
    "            ans.append(nums[i])\n",
    "            nums.pop(i)\n",
    "            k = k-(i-1)*sta[n-1]\n",
    "            n-=1\n",
    "        ans.append(nums[-1])\n",
    "        a = \"\".join([str(i) for i in ans])\n",
    "        return a\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getPermutation(self, n: int, k: int) -> str:\n",
    "            re = ''\n",
    "            base = math.factorial(n-1)\n",
    "            val_pool = [str(val) for val in range(1, n+1)]\n",
    "            count = n-1\n",
    "            k = k - 1\n",
    "            while count>0:\n",
    "                tmp = (k//base)      \n",
    "                # print(k, base, tmp, val_pool[tmp])\n",
    "                re += val_pool[tmp]\n",
    "                val_pool.remove(val_pool[tmp])\n",
    "                k=k%base\n",
    "                base //=count\n",
    "                count -= 1\n",
    "\n",
    "            re += val_pool[0]\n",
    "            return  re \n",
    "\n",
    "\n",
    "         "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getPermutation(self, n: int, k: int) -> str:\n",
    "        n_list = [i for i in range(1, n + 1)]\n",
    "\n",
    "        def factorial(num):\n",
    "            res = 1\n",
    "            for i in range(1, num + 1):\n",
    "                res *= i\n",
    "            return res\n",
    "\n",
    "        def search(remain_n_list, cur_string, remain_k):\n",
    "            print(1)\n",
    "            if remain_k == 1:\n",
    "                return cur_string + ''.join(map(str, remain_n_list))\n",
    "            if factorial(len(remain_n_list)) == remain_k:\n",
    "                return cur_string + ''.join([str(remain_n_list[i]) for i in range(len(remain_n_list) - 1, -1, -1)])\n",
    "            factorial_v = factorial(len(remain_n_list) - 1)\n",
    "            print(remain_n_list, remain_k, factorial_v)\n",
    "            cur_num_idx = (remain_k - 1) // factorial_v\n",
    "            cur_num = remain_n_list.pop(cur_num_idx)\n",
    "            remain_k = remain_k % factorial_v\n",
    "            if remain_k == 0:\n",
    "                remain_k = factorial(len(remain_n_list))\n",
    "\n",
    "            return search(remain_n_list, cur_string + str(cur_num), remain_k)\n",
    "    \n",
    "        return search(n_list, '', k)\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getPermutation(self, n: int, k: int) -> str:\n",
    "        cur, nums, ans = [1] * (n - 1), [n] * n, 1\n",
    "        for i in range(1, n):\n",
    "            ans *= i\n",
    "            cur[n - 1 - i], nums[i - 1] = ans, i\n",
    "        k, s = k - 1, ''\n",
    "        for i in range(n - 1):\n",
    "            ans, k = divmod(k, cur[i])\n",
    "            idx = nums.pop(ans)\n",
    "            s += str(idx)\n",
    "        idx = nums.pop()\n",
    "        s += str(idx)\n",
    "        return s\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def getPermutation(self, n: int, k: int) -> str:\r\n",
    "        def next_permutation(s):\r\n",
    "            break_point = -1\r\n",
    "            for i in range(len(s)-2,-1,-1):\r\n",
    "                if s[i] < s[i+1]:\r\n",
    "                    break_point = i\r\n",
    "                    break\r\n",
    "            if break_point == -1:\r\n",
    "                s = s[::-1]\r\n",
    "                return\r\n",
    "            reverse_point = -1\r\n",
    "            for i in range(len(s)-1,break_point,-1):\r\n",
    "                if s[i] > s[break_point]:\r\n",
    "                    reverse_point = i\r\n",
    "                    break\r\n",
    "            assert reverse_point != -1\r\n",
    "            s[break_point], s[reverse_point] = s[reverse_point], s[break_point]\r\n",
    "            s[break_point+1:] = s[break_point+1:][::-1]\r\n",
    "            return\r\n",
    "        cur_k  = 1\r\n",
    "        s = [f'{i}'for i in range(1,n+1)]\r\n",
    "        for cur_k in range(2, k+1):\r\n",
    "            next_permutation(s)\r\n",
    "        return ''.join(s)\r\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getPermutation(self, n: int, k: int) -> str:\n",
    "        def location(n,k):\n",
    "            a = 1\n",
    "            for i in range(1,n+1):\n",
    "                a*=i\n",
    "            if k/(a/n)==int(k/(a/n)):\n",
    "                return int(k/(a/n))\n",
    "            return int(k/(a/n))+1\n",
    "        def dfs(n,k,start,end,ans,l=0,before=[],cur=\"\"):\n",
    "            if l == n:  #不用len(cur)==n 因为len(cur)复杂度是O（n）\n",
    "                ans.append(cur)\n",
    "            for i in range(start,end): #根据数学规律， 第k个只能位于location(n,k)位置 \n",
    "                if not i in before:\n",
    "                    dfs(n,k,int(start/start),n+1,ans,l+1,before+[i],cur+str(i))#这里区间【int(start/start),n+1】还能优化\n",
    "        ans = []\n",
    "        start=location(n,k)\n",
    "        dfs(n,k,start,start+1,ans)\n",
    "        a = 1\n",
    "        for i in range(1,n+1):\n",
    "            a*=i\n",
    "        return ans[(k-1)%(int(a/n))]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getPermutation(self, n: int, k: int) -> str:\n",
    "        if n == 1 and k == 1:\n",
    "            return str(n)\n",
    "\n",
    "        com = 1 # 每个数后面有多少个排列\n",
    "        for i in range(1,n):\n",
    "            com *= i\n",
    "        layer, k = k//com+1, k%com\n",
    "        if k==0:\n",
    "            layer -= 1\n",
    "            k = com\n",
    "        \n",
    "        s = list(range(1, n+1))\n",
    "        s.remove(layer)\n",
    "        s = [str(i) for i in s]\n",
    "        path = str(layer)\n",
    "        res = []\n",
    "        def backtrack(s, path, res,k):\n",
    "            if len(s)==0:\n",
    "                res.append(path)\n",
    "                if len(res) == k:\n",
    "                    return res[k-1]\n",
    "            \n",
    "            else:\n",
    "                for i in range(len(s)):\n",
    "                    cur = s[i]\n",
    "                    a = backtrack(s[:i]+s[i+1:], path+cur, res,k)\n",
    "                    if a is not None:\n",
    "                        return a\n",
    "        return backtrack(s,path,res,k)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.ans = []\n",
    "\n",
    "    def getPermutation(self, n: int, k: int) -> str:\n",
    "        if n<9 :\n",
    "            str1 = ''.join([str(i) for i in range(1,1+n)])\n",
    "            return self.process(str1)[k-1]\n",
    "        elif k<=40320:\n",
    "            return '1'+self.process('23456789')[k-40321]\n",
    "        elif 40320<k<=80640:\n",
    "            return '2'+self.process('13456789')[k-40321]\n",
    "        elif  80640<k<=120960:\n",
    "            return '3' + self.process('12456789')[k - 80641]\n",
    "        elif  120960<k<=161280:\n",
    "            return '4' + self.process('12356789')[k - 120961]\n",
    "        elif  161280<k<=201600:\n",
    "            return '5' + self.process('12346789')[k - 161281]\n",
    "        elif  201600<k<=241920:\n",
    "            return '6' + self.process('12345789')[k - 201601]\n",
    "        elif  241920<k<=282240:\n",
    "            return '7' + self.process('12345689')[k - 241921]\n",
    "        elif  282240<k<=322560:\n",
    "            return '8' + self.process('12345679')[k - 282241]\n",
    "        elif  322560<k:\n",
    "            return '9' + self.process('12345678')[k - 322561]\n",
    "\n",
    "\n",
    "    def process(self, str1):\n",
    "        if len(str1)==0:\n",
    "            return [[]]\n",
    "        if len(str1) == 1:\n",
    "            return [str1]\n",
    "        ans = []\n",
    "        for i in range(len(str1)):\n",
    "\n",
    "            cur_c = str1[i]\n",
    "\n",
    "            t_s = str1[0:i] + str1[i + 1:]\n",
    "            t_ans = self.process(t_s)\n",
    "\n",
    "            for t_list in t_ans:\n",
    "                # for v in t_list:\n",
    "                    # print(cur_c,v)\n",
    "                ans.append(cur_c + t_list)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getPermutation(self, n: int, k: int) -> str:\n",
    "        \n",
    "        def getPermutation_str(s):\n",
    "            if len(s) == 0:\n",
    "                return []\n",
    "            if len(s) == 1:\n",
    "                return [s]\n",
    "            result = []\n",
    "            for i in range(len(s)):\n",
    "                tmp = getPermutation_str(s[0:i]+s[i+1:])\n",
    "                for t in tmp:\n",
    "                    result.append(s[i]+t)\n",
    "            return result\n",
    "        \n",
    "        s = ''.join([str(_) for _ in range(1, n+1)])\n",
    "        if len(s) == 1:\n",
    "            return s\n",
    "        a = 1\n",
    "        for i in range(1, n):\n",
    "            a *= i\n",
    "        t = (k-1) // a \n",
    "        m = (k-1) % a\n",
    "        return s[t] + getPermutation_str(s[0:t]+s[t+1:])[m]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getPermutation(self, n: int, k: int) -> str:\n",
    "        # 思路:先确定以哪个数字开头，观察得到以1开头的有(n-1)!,2开头的有(n-1)!\n",
    "        # start求出以哪个数字开头,比如题目是[3,3]，此时judge=2,start = 2\n",
    "        judge = math.factorial(n - 1)\n",
    "        start = (k-1) // judge + 1\n",
    "        # 先对其他数字全排列\n",
    "        nums = [i+1 for i in range(n) if (i+1)!=start]\n",
    "        permutations = list(itertools.permutations(nums))\n",
    "        # 最后把start插到第0个位置\n",
    "        return f'{start}'+''.join(str(permutation) for permutation in permutations[k - (start - 1) * judge - 1])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getPermutation(self, n: int, k: int) -> str:\n",
    "        def getAllPermute(allPermute, nums, curr, used, depth):\n",
    "            if depth == len(nums):\n",
    "                allPermute.append(curr[:])\n",
    "                return\n",
    "            for i in range(n-1):\n",
    "                if not used[i]:\n",
    "                    curr.append(nums[i])\n",
    "                    used[i] = True\n",
    "                    getAllPermute(allPermute, nums, curr, used, depth+1)\n",
    "                    used[i] = False\n",
    "                    curr.pop()\n",
    "\n",
    "        if n == 1:\n",
    "            return \"1\"\n",
    "        numPer = 1\n",
    "        for i in range(1,n):\n",
    "            numPer = numPer * i\n",
    "        numFirst = (k-1) // numPer + 1\n",
    "        nums = [i for i in range(1,n+1) if i != numFirst]\n",
    "        curr = []\n",
    "        used = [False for i in range(n-1)]\n",
    "        depth = 0\n",
    "        allPermute = []\n",
    "        getAllPermute(allPermute, nums, curr, used, depth)\n",
    "        ansList = allPermute[k%numPer-1]\n",
    "        ans = str(numFirst)\n",
    "        for temp in ansList:\n",
    "            ans = ans + str(temp)\n",
    "        return ans\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getPermutation(self, n: int, k: int) -> str:\n",
    "        def dfs(nums, path, used, res, start):\n",
    "            if len(path) > 0 and path[0] != start:\n",
    "                return\n",
    "            if len(path) == len(nums):\n",
    "                res.append(path[:])\n",
    "                return\n",
    "            for i in range(len(nums)):\n",
    "                if used[i] == True:\n",
    "                    continue\n",
    "                used[i] = True\n",
    "                path.append(nums[i])\n",
    "                dfs(nums, path, used, res, start)\n",
    "                path.pop()\n",
    "                used[i] = False\n",
    "        nums = [i for i in range(1, n+1)]\n",
    "        used = [False] * len(nums)\n",
    "        res = []\n",
    "        def num(n):\n",
    "            res = 1\n",
    "            if n == 0:\n",
    "                return res\n",
    "            for i in range(1, n+1):\n",
    "                res = res * i\n",
    "            return res\n",
    "        start = int((k-1) / num(n-1))\n",
    "        dfs(nums, [], used, res, start+1)\n",
    "        return ''.join(str(i) for i in res[k-1-start*num(n-1)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def dfs(self, n, index, traverse_items, items, ans, k):\n",
    "        if len(items) == n:\n",
    "            ans.append(items)\n",
    "            return ans\n",
    "\n",
    "        for i in traverse_items:\n",
    "            items.append(i)\n",
    "            traverse_items_copy = traverse_items.copy()\n",
    "            traverse_items_copy.remove(i)\n",
    "            ans = self.dfs(n, index, traverse_items_copy, items, ans, k)\n",
    "            if len(ans) == k:\n",
    "                return ans\n",
    "            items.pop()\n",
    "        return ans\n",
    "    \n",
    "    def getPermutation(self, n: int, k: int) -> str:\n",
    "        traverse_items = [i for i in range(1, n+1)]\n",
    "        items = []\n",
    "        ans = []\n",
    "        last_items = self.dfs(n, 0, traverse_items, items, ans, k)[-1]\n",
    "        res = ''\n",
    "        for item in last_items:\n",
    "            res += str(item)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dfs(self,res,temp,visit,nums:List[int],j):\n",
    "        visit[j]=1\n",
    "        temp.append(nums[j]) \n",
    "        for k in range(len(nums)):\n",
    "            if visit[k]==0:\n",
    "                self.dfs(res,temp,visit,nums,k)\n",
    "        if len(temp)==len(nums):\n",
    "            res.append([temp[i] for i in range(len(temp))])\n",
    "        temp.pop()\n",
    "        visit[j]=0\n",
    "\n",
    "    def permute(self, res,nums: List[int],index) -> List[List[int]]:\n",
    "        temp=[]\n",
    "        visit=[0 for _ in range(len(nums))]\n",
    "        self.dfs(res,temp,visit,nums,index)\n",
    "        return res\n",
    "    def getPermutation(self, n: int, k: int) -> str:\n",
    "        if n==1:\n",
    "            return '1'\n",
    "        temp=[i for i in range(1,n+1)]\n",
    "        m=1\n",
    "        for i in range(1,n):\n",
    "            m*=i\n",
    "        res=[]\n",
    "        index=k//m\n",
    "        index=index-1 if k%m==0 else index\n",
    "        k=k%m-1 if k%m!=0 else m-1\n",
    "        self.permute(res,temp,index)\n",
    "        return \"\".join(str(res[k][i]) for i in range(n))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = int(1e9 + 7)\n",
    "fac = [1]\n",
    "ifac = [1]\n",
    "for i in range(1, int(1e5) + 10):\n",
    "    fac.append((fac[-1] * i) % MOD)\n",
    "    ifac.append((ifac[-1] * pow(i, MOD - 2, MOD)) % MOD)\n",
    "def calPerm(s, rank):\n",
    "    \"\"\"求在所有排列中,字典序第几小(rank>=0)是谁\"\"\"\n",
    "    n = len(s)\n",
    "    counter = Counter(s)\n",
    "    keys = sorted(counter)\n",
    "\n",
    "    res = []\n",
    "    for i in range(n):\n",
    "        for char in keys:\n",
    "            if counter[char] == 0:\n",
    "                continue\n",
    "            counter[char] -= 1\n",
    "            suf = fac[n - i - 1]  # factorial(n-i-1)\n",
    "            for count in counter.values():\n",
    "                suf *= ifac[count]  # ! factorial(count)\n",
    "                suf %= MOD\n",
    "            if suf > rank:\n",
    "                res.append(char)\n",
    "                break\n",
    "            else:\n",
    "                rank -= suf\n",
    "                counter[char] += 1\n",
    "    return res\n",
    "class Solution:\n",
    "    def getPermutation(self, n: int, k: int) -> str:\n",
    "        nums=list(range(1,n+1))\n",
    "        res=calPerm(nums,k-1)\n",
    "        return \"\".join([str(i) for i in res])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getPermutation(self, n: int, k: int) -> str:\n",
    "        if n == 1:\n",
    "            return '1' if k == 1 else ''\n",
    "        if k == 1:\n",
    "            return ''.join([str(x) for x in range(1, n+1)])\n",
    "        self.n = n\n",
    "        self.k = k\n",
    "        self.res = []\n",
    "\n",
    "        each_choice = 1\n",
    "        for i in range(n):\n",
    "            if i == 0:\n",
    "                continue\n",
    "            each_choice *= i\n",
    "        start_num = 0\n",
    "        k_copy = k\n",
    "        while k_copy > 0:\n",
    "            k_copy -= each_choice\n",
    "            start_num += 1\n",
    "\n",
    "        self.num_res = k - each_choice * (start_num - 1)\n",
    "        self.start_num = start_num\n",
    "        self.backtrack([])\n",
    "\n",
    "        return ''.join([str(x) for x in self.res[-1]])\n",
    "    \n",
    "    def backtrack(self, track):\n",
    "        if len(self.res) == self.num_res:\n",
    "            return\n",
    "        if len(track) == self.n:\n",
    "            self.res.append([x for x in track])\n",
    "            return\n",
    "        \n",
    "        for i in range(1, self.n + 1):\n",
    "            if len(self.res) == self.num_res:\n",
    "                break\n",
    "            if len(track) == 1 and track[0] != self.start_num:\n",
    "                continue\n",
    "            if i not in track:\n",
    "                track.append(i)\n",
    "                self.backtrack(track)\n",
    "                track.pop()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getPermutation(self, n: int, k: int) -> str:\n",
    "        #1.部分测试用例超时\n",
    "        # res = []\n",
    "        # def backtrack(path):\n",
    "        #     if len(path)==n:\n",
    "        #         res.append(''.join(path[:]))\n",
    "        #     for i in range(1,n+1):\n",
    "        #         if str(i) in path:continue\n",
    "        #         path.append(str(i))\n",
    "        #         backtrack(path)\n",
    "        #         path.pop()\n",
    "\n",
    "        # backtrack([])\n",
    "        # return res[k-1]\n",
    "\n",
    "        #2.提前剪枝\n",
    "        res = []\n",
    "        factorial = [1 for _ in range(n + 1)]\n",
    "        for i in range(2, n + 1):\n",
    "            factorial[i] = factorial[i - 1] * i\n",
    "\n",
    "        def backtrack(index,path,k):\n",
    "            if len(path)==n:\n",
    "                res.append(''.join(path[:]))\n",
    "            cnt = factorial[n-1-index]\n",
    "            for i in range(1,n+1):\n",
    "                if str(i) in path:continue\n",
    "                if cnt < k:\n",
    "                    k -= cnt\n",
    "                    continue\n",
    "                path.append(str(i))\n",
    "                backtrack(index+1,path,k)\n",
    "                path.pop()\n",
    "                \n",
    "        backtrack(0,[],k)\n",
    "        return res[0]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    allList = []\n",
    "\n",
    "    def childJoin(self, preList: List, remainList: List, k: int):\n",
    "        if len(Solution.allList) >= k:\n",
    "            return\n",
    "        if len(remainList) == 1:\n",
    "            Solution.allList.append(preList + [str(remainList[0])])\n",
    "        for i in range(len(remainList)):\n",
    "            nextRemainList = copy.copy(remainList)\n",
    "            nextPreList = preList + [str(nextRemainList[i])]\n",
    "            del nextRemainList[i]\n",
    "            self.childJoin(nextPreList, nextRemainList, k)\n",
    "\n",
    "    def getPermutation(self, n: int, k: int) -> str:\n",
    "        if n == 1:\n",
    "            return str(1)\n",
    "        Solution.allList = []\n",
    "        initList = list(range(1, n + 1))\n",
    "        totalNum = reduce(lambda x, y: x * y, initList)\n",
    "\n",
    "        everyNum = totalNum / n\n",
    "        firstIndex = int(k / everyNum)\n",
    "        if k % everyNum == 0:\n",
    "            firstIndex -= 1\n",
    "        firstNum = initList[firstIndex]\n",
    "        del initList[firstIndex]\n",
    "\n",
    "        k = int(k - (firstIndex) * everyNum)\n",
    "        self.childJoin([str(firstNum)], initList, k)\n",
    "\n",
    "        joinList = Solution.allList[k - 1]\n",
    "        return \"\".join(joinList)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getPermutation(self, n: int, k: int) -> str:\n",
    "        import math\n",
    "        import numpy as np\n",
    "        list_set = list(np.arange(1,n+1))\n",
    "        ret_str = ''\n",
    "        n_fact = math.factorial(n)\n",
    "        for i in range(n,0,-1):\n",
    "            n_fact = n_fact / i\n",
    "            m = math.ceil((k) / n_fact) - 1\n",
    "            ret_str += str(list_set[m])\n",
    "            list_set.remove(list_set[m])\n",
    "            k = k % n_fact\n",
    "            # n -= 1\n",
    "        return ret_str"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getPermutation(self, n: int, k: int) -> str:\n",
    "        def permute(nums):\n",
    "            path = []\n",
    "            permutations = []\n",
    "            def dfs(nums):\n",
    "                if not nums:\n",
    "                    permutations.append(path[:])\n",
    "                    return  # 别忘了return\n",
    "                for i in range(len(nums)):\n",
    "                    path.append(nums[i])\n",
    "                    dfs(nums[:i]+nums[i+1:])\n",
    "                    path.pop()\n",
    "            dfs(nums)\n",
    "            return permutations\n",
    "        # 思路:先确定以哪个数字开头，观察得到以1开头的有(n-1)!,2开头的有(n-1)!\n",
    "        # start求出以哪个数字开头,比如题目是[3,3]，此时judge=2,start = 2\n",
    "        judge = math.factorial(n - 1)\n",
    "        start = (k-1) // judge + 1\n",
    "        # 先对其他数字全排列\n",
    "        nums = [i+1 for i in range(n) if (i+1)!=start]\n",
    "        # 再把start插到第0个位置\n",
    "        permutations = [[start]+permutation for permutation in permute(nums)]\n",
    "        return ''.join(str(x) for x in  permutations[k - (start - 1) * judge - 1])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getPermutation(self, n: int, k: int) -> str:\n",
    "        import numpy as np\n",
    "        factorial = [1]\n",
    "        for i in range(2, n):\n",
    "            factorial.append(factorial[-1]*i)\n",
    "        \n",
    "        nums = [i+1 for i in range(n)]\n",
    "        res = ''\n",
    "        i = n - 2\n",
    "        while len(res) < n-1:\n",
    "            tmp = int(np.ceil((k*1.0)/factorial[i]))-1\n",
    "            digit = nums[tmp]\n",
    "            nums.pop(tmp)\n",
    "            res += str(digit)\n",
    "            k -= tmp * factorial[i]\n",
    "            i -= 1\n",
    "        res += str(nums[0])\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getPermutation(self, n: int, k: int) -> str:\n",
    "        nums=[x for x in range(1,n+1)]\n",
    "        nums2=[]\n",
    "        temp=0\n",
    "        for num in itertools.permutations(nums, n):\n",
    "            temp=0\n",
    "            for i in range(n):\n",
    "                temp=temp*10+num[i]\n",
    "            nums2.append(temp)\n",
    "            \n",
    "       \n",
    "        return str(nums2[k-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getPermutation(self, n: int, k: int) -> str:\n",
    "        listN = [ i for i in range(1,n+1)]\n",
    "        #print(listN)\n",
    "        res = []\n",
    "        tmp = \"\"     \n",
    "        size = len(listN)\n",
    "        depth = 0\n",
    "        flag=0\n",
    "        #print(nums)\n",
    "        def callback(candidates,depth,size,tmp,res,k):\n",
    "            if depth == size:\n",
    "                if int(tmp) > n:\n",
    "                    #print(\"#####\")\n",
    "                    res.append(int(tmp))\n",
    "                    #print(res)\n",
    "                return\n",
    "            for index in range(len(candidates)):\n",
    "                tmp2=candidates.copy()\n",
    "                tmp2.pop(index)\n",
    "                if len(res) < k:\n",
    "                    callback(tmp2,depth+1,size,tmp+str(candidates[index]),res,k)\n",
    "        \n",
    "        callback(listN,depth,size,tmp,res,k)\n",
    "        #print(res)\n",
    "        if n==1:return \"1\"\n",
    "        else:return str(res[-1])\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from itertools import permutations\n",
    "class Solution:\n",
    "    def getPermutation(self, n: int, k: int) -> str:\n",
    "        #Num = (str(i) for i in range(1, n + 1))\n",
    "        #data = sorted((int(''.join(x)) for x in permutations((str(i) for i in range(1, n + 1)), n)))\n",
    "        #return str(data[k-1])\n",
    "        return str(sorted((int(''.join(x)) for x in permutations((str(i) for i in range(1, n + 1)), n)))[k-1])\n",
    "        \n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getPermutation(self, n: int, k: int) -> str:\n",
    "        l_fac= []\n",
    "        l_fac.append(1)\n",
    "        p = 1\n",
    "        for i in range(1,n+1):\n",
    "            p *= i\n",
    "            l_fac.append(p)\n",
    "        def dfs(cur,visited,k,h):\n",
    "            if len(cur) == n:\n",
    "                if k == 1:\n",
    "                    res.append(cur)\n",
    "                return\n",
    "            for i in range(1,n+1):\n",
    "                if visited[i] == True:\n",
    "                    continue\n",
    "                if k > l_fac[h-1]:\n",
    "                    k -= l_fac[h-1]\n",
    "                    continue\n",
    "                cur += str(i)\n",
    "                visited[i] = True\n",
    "                dfs(cur,visited,k,h-1)\n",
    "                cur = cur[:-1]\n",
    "                visited[i] = False\n",
    "        cur = \"\"\n",
    "        res = []\n",
    "        visited = [False for i in range(n+1)]\n",
    "        dfs(cur,visited,k,n)\n",
    "        return res[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from itertools import permutations\n",
    "class Solution:\n",
    "    def getPermutation(self, n: int, k: int) -> str:\n",
    "        list_nums = [str(i) for i in range(1,n+1)]\n",
    "        res = sorted([int(''.join(i)) for i in permutations(list_nums,n)])\n",
    "        return str(res[k-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def getPermutation(self, n: int, k: int) -> str:\n",
    "        def Factorial(n):\n",
    "            if n == 1:\n",
    "                return 1\n",
    "\n",
    "            else:\n",
    "                return n * Factorial(n-1)\n",
    "\n",
    "        s = \"\"\n",
    "        lst = np.arange(1,n + 1)\n",
    "        lst = lst.tolist()\n",
    "        count = n\n",
    "        while len(s) < n - 1:\n",
    "            fact = Factorial(count - 1)\n",
    "            for i in range(1,count + 1):\n",
    "                if k <= i * fact:\n",
    "                    s += str(lst[i - 1])\n",
    "                    lst.pop(i - 1)\n",
    "                    count -= 1\n",
    "                    k -= (i - 1) * fact\n",
    "                    break\n",
    "\n",
    "        s += str(lst[0])\n",
    "        return s\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def getPermutation(self, n: int, k: int):\n",
    "        ##统计第一位\n",
    "        p=[]\n",
    "        q=[]\n",
    "        num=0\n",
    "        pre=[]\n",
    "        all=[i for i in range(1,n+1)]\n",
    "        d=list(set(all)-set(pre))\n",
    "        d.sort()\n",
    "\n",
    "        num_list=[0]\n",
    "        while(len(pre)<n):\n",
    "            for i in d:\n",
    "                tmp = math.factorial(n-len(pre)-1)\n",
    "                num+=tmp\n",
    "                if(k<=num):\n",
    "                    pre.append(i)\n",
    "                    k=k-(num-tmp)\n",
    "                    num=0\n",
    "                    break\n",
    "\n",
    "            d = list(set(all) - set(pre))\n",
    "            d.sort()\n",
    "\n",
    "        res=''\n",
    "        for p in pre:res=res+str(p)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def getPermutation(self, n: int, k: int) -> str:\r\n",
    "        import math\r\n",
    "        self.temp = []\r\n",
    "        self.path = []\r\n",
    "        self.index = 0\r\n",
    "\r\n",
    "        #从最近的排列开始，逐渐回溯,start是groups对应的最近的排列\r\n",
    "        #left是k对应的在对应排列的位置\r\n",
    "       \r\n",
    "        self.start = math.ceil(k/math.factorial(n-1))\r\n",
    "        left = k - (self.start-1)*math.factorial(n-1)\r\n",
    "\r\n",
    "        def backtrack(n,k):\r\n",
    "            #跳过start之前的排列\r\n",
    "            if self.index == k:\r\n",
    "                return\r\n",
    "            if len(self.temp) == n:\r\n",
    "                self.path.append(self.temp[:])\r\n",
    "                self.index += 1\r\n",
    "                return\r\n",
    "            for i in range(1, n+1):\r\n",
    "                if i in self.temp:\r\n",
    "                    continue\r\n",
    "                if len(self.temp) == 0 and i < self.start:\r\n",
    "                    continue\r\n",
    "                self.temp.append(i)\r\n",
    "                backtrack(n,k)\r\n",
    "                self.temp.pop()\r\n",
    "        backtrack(n,left)\r\n",
    "        return ''.join([str(i) for i in self.path[-1]])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getPermutation(self, n: int, k: int) -> str:\n",
    "\n",
    "\n",
    "        tempN = [str(i) for i in range(1, n + 1)]\n",
    "\n",
    "        res = []\n",
    "\n",
    "        def generate(path):\n",
    "            if len(path) == n:\n",
    "                return res.append(path)\n",
    "            for i in range(n):\n",
    "                if tempN[i] not in path:\n",
    "                    generate(path + [tempN[i]])\n",
    "        cur = 1\n",
    "        for i in range(1, n):\n",
    "            cur *= i\n",
    "        for i in range(n):  \n",
    "            if cur * (i+1) >= k:\n",
    "                k -= cur * (i+1)\n",
    "                generate([tempN[i]])\n",
    "                break\n",
    "        return ''.join(res[k - 1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getPermutation(self, n: int, k: int) -> str:\n",
    "        if n==1:\n",
    "            return str(1)\n",
    "        res=[]\n",
    "        path=[]\n",
    "        visited=[False] * (n+1)\n",
    "        fac = [1] * (n+1)\n",
    "        for i in range(2,n+1):\n",
    "            fac[i]=fac[i-1]*i\n",
    "                \n",
    "        # fac[n] 表示总的方案数，fac[n-1]表示以每个数字开头的方案数\n",
    "        range_k = k//fac[n-1]+1 if k%fac[n-1]!=0 else k//fac[n-1]\n",
    "        def dfs(curID,n):\n",
    "            if visited[curID]:\n",
    "                return\n",
    "            path.append(curID)\n",
    "            visited[curID]=True\n",
    "            if len(path)==n:\n",
    "                res.append(path.copy())\n",
    "                visited[curID]=False\n",
    "                path.pop()\n",
    "                return\n",
    "            for i in range(1,n+1):\n",
    "                dfs(i,n)\n",
    "            visited[curID]=False\n",
    "            path.pop()\n",
    "        dfs(range_k,n)\n",
    "        # return ''.join(str(i) for i in (res[k-1]))\n",
    "        i=k%fac[n-1]-1\n",
    "        # i=fac[n]-k\n",
    "        return ''.join(str(i) for i in (res[i]))\n",
    "        # return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    result = []\n",
    "    is_find = False\n",
    "    k = 0\n",
    "    def helper(self, single_ : str, nums : List[str]):\n",
    "        if not self.is_find:\n",
    "            if len(nums) == 1:\n",
    "                self.result.append(single_ + nums[0])\n",
    "                if len(self.result) == self.k:\n",
    "                    self.is_find =True\n",
    "            else:\n",
    "                for i in nums:\n",
    "                    nums_copy = nums.copy()\n",
    "                    nums_copy.remove(i)\n",
    "                    self.helper(single_ + i , nums_copy)\n",
    "\n",
    "\n",
    "    def getPermutation(self, n: int, k: int) -> str:\n",
    "        self.k = k\n",
    "        self.result = []\n",
    "        if n == 1:\n",
    "            return '1'\n",
    "        init_list = [str(i) for i in range(1,n+1)]\n",
    "        self.helper('',init_list)        \n",
    "        # self.result = sorted(self.result,key = lambda  x :int(x))\n",
    "        # print(self.result)\n",
    "        return self.result[k-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def factorial_dp(num):\n",
    "    if num == 0:\n",
    "        return 1\n",
    "    dp = [1] * (num + 1)\n",
    "    for i in range(1,num+1):\n",
    "        dp[i] = dp[i-1]*i\n",
    "    return dp[num]\n",
    "class Solution:\n",
    "    def getPermutation(self, n: int, k: int) -> str:\n",
    "        k=k-1\n",
    "        nums=list(range(1,n+1))\n",
    "        nums.insert(0,nums[k // factorial_dp(n - 1)])\n",
    "        nums=nums[0:k // factorial_dp(n - 1)+1]+nums[k // factorial_dp(n - 1)+2:]\n",
    "        s=k-(k // factorial_dp(n - 1))*factorial_dp(n-1)+1\n",
    "        def bt(nums,path):\n",
    "            if len(path)==len(nums):\n",
    "                if len(res)==s:\n",
    "                    return\n",
    "                else:\n",
    "                    res.append(copy.deepcopy(path))\n",
    "            for i in range(len(nums)):\n",
    "                if nums[i] not in path:\n",
    "                    path.append(nums[i])\n",
    "                    bt(nums,path)\n",
    "                    path.pop()\n",
    "                if i!=0 and len(res)==s:\n",
    "                    break\n",
    "        res=[]\n",
    "        bt(nums,[])\n",
    "        return \"\".join(list(map(str,res[-1])))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getPermutation(self, n: int, k: int) -> str:\n",
    "        s = list()\n",
    "        allSort = list()\n",
    "        sums = 1\n",
    "        # 初始化排序\n",
    "        for i in range(n):\n",
    "            s.append(str(i+1))\n",
    "            sums *= (i+1)\n",
    "        allSort.append(''.join(s))\n",
    "        while len(allSort) <= k:\n",
    "            i = n - 2\n",
    "            # 获取较小数\n",
    "            while i >= 0 and s[i] >= s[i+1]:\n",
    "                i -= 1\n",
    "            # 若存在较小数，即整个序列不为最大序列\n",
    "            if i >= 0:\n",
    "                j = len(s) - 1\n",
    "                # 获取较大数\n",
    "                while j >= 0 and s[i] >= s[j]:\n",
    "                    j -= 1\n",
    "                # 交换较小数和较大数\n",
    "                s[i], s[j] = s[j], s[i]\n",
    "            # 获取重排序列并重排\n",
    "            left, right = i + 1, len(s) - 1\n",
    "            while left < right:\n",
    "                s[left], s[right] = s[right], s[left]\n",
    "                left += 1\n",
    "                right -= 1\n",
    "            allSort.append(''.join(s))\n",
    "        return allSort[k-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getPermutation(self, n: int, k: int) -> str:\n",
    "        def get_permu(s: str, cur_s: str, result=List[str]):\n",
    "            if not s:\n",
    "                result.append(cur_s)\n",
    "                return\n",
    "            if len(result) < k:\n",
    "                for i in range(len(s)):\n",
    "                    get_permu(s[:i] + s[i + 1:], cur_s + s[i], result)\n",
    "\n",
    "        s = ''\n",
    "        for i in range(1, n + 1):\n",
    "            s += str(i)\n",
    "        result = []\n",
    "        get_permu(s, '', result)\n",
    "        return result[- 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getPermutation(self, n, k) :\n",
    "        nums = [str(x+1) for x in range(n)]\n",
    "        self.res = []\n",
    "        self.k = k\n",
    "        self.visited = [False]*len(nums)\n",
    "        self.dfs(nums, \"\")\n",
    "        return self.res[-1] if self.res else \"\"\n",
    "    \n",
    "    def dfs(self, nums, path):\n",
    "        if len(path) == len(nums):\n",
    "            # attention, 此处不需要copy，因为path是str\n",
    "            self.res.append(path)\n",
    "            return\n",
    "        \n",
    "        if len(self.res) == self.k:\n",
    "            # 快速退出\n",
    "            return\n",
    "\n",
    "        for i, num in enumerate(nums):\n",
    "            if self.visited[i]:\n",
    "                continue\n",
    "\n",
    "            self.visited[i] = True\n",
    "            self.dfs(nums, path+num)\n",
    "            self.visited[i] = False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getPermutation(self, n: int, k: int) -> str:\n",
    "        import itertools\n",
    "        s=[]\n",
    "        s1=[]\n",
    "        \n",
    "        for i in range(n):\n",
    "            s.append(str(i+1))\n",
    "        s2=itertools.permutations(s,n)\n",
    "        for i in s2:\n",
    "            \n",
    "            s1.append(''.join(i))\n",
    "\n",
    "        s1.sort()\n",
    "        \n",
    "        return s1[k-1]\n",
    "        \n",
    "        \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from scipy.special import perm\n",
    "class Solution:\n",
    "    def dfs(self, n, index, k, s, map):\n",
    "        #print(s, len(s), index)\n",
    "        if len(s) == n and index[0] == k:\n",
    "            return s\n",
    "        elif len(s) == n and index[0] < k:\n",
    "            return None\n",
    "        for i in range(n):\n",
    "            if map[i+1] == 1: continue\n",
    "            map[i+1] = 1\n",
    "            s1 = s+str(i+1)\n",
    "            res = \"\"\n",
    "            if len(s1) == n:\n",
    "                index[0] += 1\n",
    "                res = self.dfs(n, index, k, s1, map)\n",
    "            else:\n",
    "                res = self.dfs(n, index, k, s1, map)\n",
    "            if res:\n",
    "                return res\n",
    "            map[i+1] = 0\n",
    "        return None\n",
    "    def getPermutation(self, n: int, k: int) -> str:\n",
    "        if n == 1 and k == 1:\n",
    "            return str(n)\n",
    "        map = dict()\n",
    "        for i in range(n):\n",
    "            map[i+1] = 0\n",
    "        c = int(perm(n-1, n-1))\n",
    "        num = int((k-1)//c)\n",
    "        map[num+1] = 1\n",
    "        return self.dfs(n, [int(num*c)], k, str(num+1)+\"\", map)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getPermutation(self, n: int, k: int) -> str:\n",
    "        def v1(n,k):\n",
    "            ca={}\n",
    "            vis=[]\n",
    "            def perm(first=0):\n",
    "                if len(res)>k:return\n",
    "                if first ==n:\n",
    "                    res.append(nums[:])\n",
    "                for i in range(first, n):\n",
    "                    nums[first], nums[i] = nums[i], nums[first]\n",
    "                    perm(first + 1)\n",
    "                    nums[first], nums[i] = nums[i], nums[first] # 撤销操作\n",
    "            res =[]\n",
    "            nums = [i for i in range(1,n+1)]\n",
    "            perm()\n",
    "            rr= sorted([ls for ls in res])[k-1]\n",
    "            return ''.join(map(str,rr))\n",
    "\n",
    "        def v0(nums,k):\n",
    "            ca={}\n",
    "            def perm(nums):\n",
    "                if len(res)>k:return []\n",
    "                tnu = tuple(nums)\n",
    "                ln = len(nums)\n",
    "                if tnu in ca: return ca[tnu]\n",
    "                if ln<=1:\n",
    "                    r= [nums]\n",
    "                else:\n",
    "                    r = []\n",
    "                    for ii in range(ln):\n",
    "                        tli = [ [nums[ii]] + el for el in perm(nums[:ii]+nums[ii+1:])]\n",
    "                        for el in tli: \n",
    "                            r.append(el)\n",
    "                            if ln ==n and len(res)<=k:\n",
    "                                res.append(el)\n",
    "                ca[tnu]=r\n",
    "                return r     \n",
    "            res=[]\n",
    "            #nums = [i for i in range(1,n+1)]\n",
    "            r=perm(nums)\n",
    "            rr= sorted([ls for ls in r])[k-1]\n",
    "            return ''.join(map(str,rr))\n",
    "\n",
    "        if n<9:\n",
    "            return v0([i for i in range(1,n+1)],k)\n",
    "        else:\n",
    "            fa8 = math.factorial(8)\n",
    "            print(fa8)\n",
    "            m =k//fa8\n",
    "            lft= k%fa8\n",
    "            return str(m+1)+v0([i for i in range(1,n+1) if i!=m+1],lft)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "a=[[\"1\"],[\"12\",\"21\"]]\n",
    "for i in range(1,8):\n",
    "    ans=[]\n",
    "    num=i+2\n",
    "    for xx in a[i]:\n",
    "        for index in range(len(xx)+1):\n",
    "            ans.append(xx[0:index]+str(num)+xx[index:])\n",
    "    ans.sort()\n",
    "    a.append(ans)\n",
    "class Solution:\n",
    "    def getPermutation(self, n: int, k: int) -> str:\n",
    "        return a[n-1][k-1]\n",
    "Solution().getPermutation(9,1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getPermutation(self, n: int, k: int) -> str:\n",
    "\n",
    "        def dfs(size, k, path, res, used):\n",
    "            if len(path) == size:\n",
    "                res.append(\"\".join(path))\n",
    "                return\n",
    "\n",
    "            for i in range(1, size+1):\n",
    "                if not used[i]:\n",
    "                    path.append(str(i))\n",
    "                    used[i] = True\n",
    "                    dfs(size, k, path, res, used)\n",
    "                    if len(res) == k:\n",
    "                        return res[-1]\n",
    "                    path.pop()\n",
    "                    used[i] = False  \n",
    "\n",
    "        path, res = [], []\n",
    "        used = [False] * (n+1)\n",
    "        return dfs(n, k, path, res, used)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getPermutation(self, n: int, k: int) -> str:\n",
    "        \n",
    "        def backtrack(state, choices, res, used):\n",
    "            if len(state) == n:\n",
    "                res.append(state)\n",
    "                if len(res) == k: return True\n",
    "                else: return False\n",
    "\n",
    "            for choice in choices:\n",
    "                if choice in used: continue\n",
    "                used.append(choice)\n",
    "                if backtrack(state + str(choice), choices, res, used): return True\n",
    "                used.pop()\n",
    "            return False\n",
    "\n",
    "\n",
    "        state = \"\"\n",
    "        choices = [i for i in range(1, n + 1)]\n",
    "        res = []\n",
    "        used = []\n",
    "        backtrack(state, choices, res, used)\n",
    "        return res[-1]\n",
    "\n",
    "           "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getPermutation(self, n: int, k: int) -> str:\n",
    "        #dfs+回溯：回溯一定要记得path和原数组都要复原，才能遍历每条分支\n",
    "        #直接dfs完后会超时，因为result的总的可能结果很多，所以增加一条if，只需要result生成到第k个即可\n",
    "        result=[]\n",
    "        def  dfs(nums,path,result):\n",
    "            if len(result)>k:\n",
    "                return result\n",
    "            elif not nums:\n",
    "                result.append(\"\".join(path))\n",
    "                # print(path)\n",
    "                return result\n",
    "            else:\n",
    "                for i in range(len(nums)):\n",
    "                    x=nums.pop(i)\n",
    "                    path.append(x)\n",
    "                    dfs(nums,path,result)\n",
    "                    path.pop() #path跳出上一个dfs\n",
    "                    nums.insert(i,x)\n",
    "        nums=[str(i+1) for i in range(n)]\n",
    "        dfs(nums,[],result)     \n",
    "        result.sort()\n",
    "        return result[k-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getPermutation(self, n: int, k: int):\n",
    "        lis = list(range(1, n + 1))\n",
    "        output = []\n",
    "        cur = []\n",
    "        index = None\n",
    "        times = []\n",
    "        def gp(lis, cur, index):\n",
    "            if len(times) == k:\n",
    "                return\n",
    "            temp = lis.copy()\n",
    "            if index == 0 or index:\n",
    "                temp.pop(index)\n",
    "            if not temp:\n",
    "                times.append(0)\n",
    "                if len(times) == k:\n",
    "                    output.append(cur)\n",
    "                return\n",
    "            for i in range(len(temp)):\n",
    "                gp(temp, cur + [temp[i]], i)\n",
    "        gp(lis, cur, index)\n",
    "        for i in range(len(output[0])):\n",
    "            output[0][i] = '{}'.format(output[0][i])\n",
    "        return ''.join(output[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getPermutation(self, n: int, k: int) -> str:\n",
    "        \n",
    "        def gen(n):\n",
    "            if n == 1:\n",
    "                return [\"1\"]\n",
    "            r = gen(n-1)\n",
    "            t,c = [],str(n)\n",
    "            for i in r:\n",
    "                for j in range(len(i)):\n",
    "                    t.append(i[:j]+c+i[j:])\n",
    "                t.append(i+c)\n",
    "            return t\n",
    "        return sorted(gen(n))[k-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getPermutation(self, n: int, k: int) -> str:\n",
    "        if k>self.nn(n):\n",
    "            return ''\n",
    "        # 从大到小排序sorted\n",
    "        # 生成一个n位长的list\n",
    "\n",
    "        list_n = list(range(1, n + 1))\n",
    "        res = self.permute(list_n)\n",
    "        res_sorted = sorted(res)\n",
    "        res_k = res_sorted[k - 1]\n",
    "        last_res = ''.join(map(str, res_k))\n",
    "        return last_res\n",
    "    def nn(self, n: int) -> int:\n",
    "        if n == 1:\n",
    "            return 1\n",
    "        return n * self.nn(n - 1)\n",
    "    def permute(self, nums: list[int]) -> list[str]:\n",
    "        # 先找到全排列\n",
    "        if len(nums) == 1:\n",
    "            return [str(nums[0])]\n",
    "        res = []\n",
    "        for sub in self.permute(nums[1:]):\n",
    "            # 去掉前后的[]\n",
    "            sub = sub.replace('[','').replace(']','')\n",
    "            for i in range(len(sub) + 1):\n",
    "                add_list =sub[:i]+str(nums[0])+sub[i:]\n",
    "                res.append(add_list)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getPermutation(self, n: int, k: int) -> str:\n",
    "        nums = []\n",
    "        check = [0]*n\n",
    "        track = \"\"\n",
    "        result = []\n",
    "        n_cump = 1\n",
    "        for i in range(n):\n",
    "            nums.append(i+1)\n",
    "            n_cump *= (i+1)\n",
    "        n_cump_pre = n_cump / n\n",
    "        branch = k // n_cump_pre\n",
    "        res = k-n_cump_pre*branch\n",
    "\n",
    "        def backtrack(track,nums,k):\n",
    "            if len(track) == n:\n",
    "                result.append(track[:])\n",
    "                #print(result)\n",
    "            if res == 0 and len(result) == n_cump_pre:\n",
    "                return\n",
    "            elif res > 0 and len(result) == res:\n",
    "                return\n",
    "            for i in range(n):\n",
    "                if str(nums[i]) in track:\n",
    "                    continue\n",
    "                if res==0 and sum(check)==0 and i < branch -1:\n",
    "                    continue\n",
    "                elif res > 0 and sum(check)==0 and i < branch:\n",
    "                    continue\n",
    "                track += str(nums[i])\n",
    "                check[i] = 1\n",
    "                backtrack(track,nums,k)\n",
    "                track = track[:-1]\n",
    "                check[i] = 0\n",
    "        backtrack(track,nums,k)\n",
    "        #return \"\".join([str(result[k-1][i]) for i in range(n)])\n",
    "        return result[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getPermutation(self, n: int, k: int) -> str:\n",
    "        \n",
    "        ans = [['']]\n",
    "        for i in range(1,n+1):\n",
    "            if i == 1:\n",
    "                ans.append(['1'])\n",
    "            elif i == 2:\n",
    "                ans.append(['12','21'])\n",
    "            else:\n",
    "                a = []\n",
    "                for m in range(i):\n",
    "                    [a.append(k[:m] + str(i) +k[m:]) for k in ans[-1]]\n",
    "                ans.append(sorted(a))\n",
    "        \n",
    "        return ans[n][k-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getPermutation(self, n: int, k: int) -> str:\n",
    "        res = []\n",
    "\n",
    "        def cal_factorial(num):\n",
    "            \"\"\"计算阶乘\"\"\"\n",
    "            factorial = 1\n",
    "            for i in range(1, num + 1):\n",
    "                factorial = factorial * i\n",
    "            return factorial\n",
    "\n",
    "        def dfs(candidates, path):\n",
    "            if len(res) == k:\n",
    "                return\n",
    "            if not candidates:\n",
    "                res.append(\"\".join(path))\n",
    "                return\n",
    "\n",
    "            can_len = len(candidates)\n",
    "            extend_len = cal_factorial(can_len-1)\n",
    "            # 走完这一步之后预计res的长度\n",
    "            for idx in range(can_len):\n",
    "                if len(res) + extend_len < k:\n",
    "                    res.extend([\"\"]*extend_len)\n",
    "                else:\n",
    "                    dfs(candidates[:idx] + candidates[idx + 1:], path + [str(candidates[idx])])\n",
    "\n",
    "        dfs(list(range(1, n + 1)), [])\n",
    "        return res[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getPermutation(self, n: int, k: int) -> str:\n",
    "        nums = []\n",
    "        for i in range(n):\n",
    "            nums.append(i+1)\n",
    "        res = []\n",
    "        path = []\n",
    "        using = [1]*len(nums)\n",
    "        def huisu():\n",
    "            # tmp = set([])\n",
    "            if len(path) == len(nums):\n",
    "                res.append(path.copy())\n",
    "                if len(res) == k:\n",
    "                    return -1\n",
    "                return 0\n",
    "            for i in range(len(nums)):\n",
    "                if using[i]:\n",
    "                    path.append(nums[i])\n",
    "                    using[i] = 0\n",
    "                    t = huisu()\n",
    "                    if t != 0:\n",
    "                        return -1\n",
    "                    path.pop()\n",
    "                    using[i] = 1\n",
    "                else:\n",
    "                    continue\n",
    "            return 0\n",
    "        def huisu_fan():\n",
    "            # tmp = set([])\n",
    "            if len(path) == len(nums):\n",
    "                res.append(path.copy())\n",
    "                if len(res) == k:\n",
    "                    return -1\n",
    "                return 0\n",
    "            for i in range(len(nums)):\n",
    "                if using[i]:\n",
    "                    path.append(nums[i])\n",
    "                    using[i] = 0\n",
    "                    t = huisu()\n",
    "                    if t != 0:\n",
    "                        return -1\n",
    "                    path.pop()\n",
    "                    using[i] = 1\n",
    "                else:\n",
    "                    continue\n",
    "            return 0\n",
    "        result = ''\n",
    "        shu = 1\n",
    "        for i in range(1,n+1):\n",
    "            shu = shu*i\n",
    "        if k>shu/2:\n",
    "            print(\"erfenchenggong\")\n",
    "            k = shu-k+1\n",
    "            nums.reverse()\n",
    "        huisu()\n",
    "        for i in res[-1]:\n",
    "            result += str(i)\n",
    "        return result\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getPermutation(self, n: int, k: int) -> str:\n",
    "        res = []\n",
    "        number = [i+1 for i in range(n)]\n",
    "        total = 1\n",
    "        for num in number:\n",
    "            total = total * num\n",
    "        print(total)\n",
    "        used = [False] * n\n",
    "        def backtack(index, path, nums):\n",
    "            if len(path) == len(nums):\n",
    "                res.append(path[:])\n",
    "                return\n",
    "            for i in range(len(nums)):\n",
    "                if used[i] == True:\n",
    "                    continue\n",
    "                if len(res) == k:\n",
    "                    break\n",
    "                used[i] = True\n",
    "                path.append(nums[i])\n",
    "                backtack(index+1, path, nums)\n",
    "                used[i] = False\n",
    "                path.pop()\n",
    "\n",
    "        def backtack1(index, path, nums):\n",
    "            if len(path) == len(nums):\n",
    "                res.append(path[:])\n",
    "                return\n",
    "            for i in range(len(nums)):\n",
    "                if used[i] == True:\n",
    "                    continue\n",
    "                if len(res) == total - k + 1:\n",
    "                    break\n",
    "                used[i] = True\n",
    "                path.append(nums[i])\n",
    "                backtack1(index+1, path, nums)\n",
    "                used[i] = False\n",
    "                path.pop()\n",
    "        if k < (total // 2): \n",
    "            backtack(0,[], number)\n",
    "        else:\n",
    "            reverse_number = number[::-1][:]\n",
    "            backtack1(0, [], reverse_number)\n",
    "        result = [str(i) for i in res[-1]]\n",
    "        return \"\".join(result)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getPermutation(self, n: int, k: int) -> str:\n",
    "        def dfs(cnt, used, subset, length):\n",
    "            if length == n:\n",
    "                res.append(subset[:])\n",
    "                return\n",
    "            for i in range(1,n+1):\n",
    "                if cnt > lookup:\n",
    "                    cnt -= lookup\n",
    "                    continue\n",
    "                if not used[i]:\n",
    "                    used[i] = True\n",
    "                    subset += str(i)\n",
    "                    dfs(cnt, used, subset, length+1)\n",
    "                    used[i] = False\n",
    "                    subset = subset[:-1]\n",
    "                    if len(res) == cnt:\n",
    "                        return \n",
    "        res = []\n",
    "        used = [False] * (n+1)\n",
    "        lookup = 1\n",
    "        for i in range(2, n):\n",
    "            lookup *= i\n",
    "        dfs(k, used, \"\", 0)\n",
    "        s = res[-1]\n",
    "        # s = \"\".join(str(i) for i in res[-1])\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getPermutation(self, n: int, k: int) -> str:\n",
    "        def dfs(depth):\n",
    "            nonlocal nums\n",
    "            if nums == k:\n",
    "                return \n",
    "\n",
    "            if depth == n:\n",
    "                ans.append(pailie.copy())\n",
    "                nums += 1\n",
    "            else:\n",
    "                for i in range(1, n+1):\n",
    "                    if str(i) not in pailie:\n",
    "                        pailie.append(str(i))\n",
    "                        dfs(len(pailie))\n",
    "                        pailie.pop()\n",
    "        \n",
    "        n_1 = 1\n",
    "        for i in range(1,n):\n",
    "            n_1 = n_1 * i \n",
    "        cir = 1\n",
    "        while k - n_1 > 0:\n",
    "            k -= n_1\n",
    "            cir += 1\n",
    "\n",
    "        pailie = [str(cir)]\n",
    "        ans = []\n",
    "        nums = 0\n",
    "        dfs(1)\n",
    "\n",
    "        return \"\".join(ans[-1])\n",
    "        \n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getPermutation(self, n: int, k: int) -> str:\n",
    "        ans=[]\n",
    "        path=[]\n",
    "        used=[0 for _ in range(n+1)]\n",
    "        fact={0:1,1:1,2:2,3:6,4:24,5:120,6:720,7:5040,8:40320,9:362880}\n",
    "        layer=fact[n-1]\n",
    "\n",
    "        for i in range(1,n+1):\n",
    "            if layer*i>=k:\n",
    "                break\n",
    "        used[i]=1\n",
    "        path.append(str(i))\n",
    "        cnt=layer*(i-1)\n",
    "\n",
    "        def track():\n",
    "            if len(path)==n:\n",
    "                nonlocal cnt\n",
    "                cnt+=1\n",
    "                ans.append(path[:])\n",
    "            if cnt==k:\n",
    "                return\n",
    "\n",
    "            for i in range(1,n+1):\n",
    "                if used[i]==1:\n",
    "                    continue\n",
    "                used[i]=1\n",
    "                path.append(str(i))\n",
    "                track()\n",
    "                path.pop(-1)\n",
    "                used[i]=0\n",
    "        track()\n",
    "        return \"\".join(ans[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getPermutation(self, n: int, k: int) -> str:\n",
    "        res = []\n",
    "        nums=[]\n",
    "        summ=0\n",
    "        for i in range(1,n+1):\n",
    "            if i==1:\n",
    "                summ=i\n",
    "            elif i!=n:\n",
    "                summ = summ*i\n",
    "            nums.append(i)\n",
    "        q = int(k/summ)\n",
    "        left = int(k%summ)\n",
    "        def dfs(nums,path):\n",
    "            if len(path)==n:\n",
    "                res.append(path)\n",
    "                return True\n",
    "            if len(res)==k-q*summ and k-q*summ!=0:\n",
    "                return False\n",
    "            for i in nums:\n",
    "                s = nums.copy()\n",
    "                s.remove(i)\n",
    "                path+=str(i)\n",
    "                flag = dfs(s,path)\n",
    "                if flag==False:\n",
    "                    return False\n",
    "                path=path[:-1]\n",
    "            return True\n",
    "        if len(nums)==1:\n",
    "            return str(1)\n",
    "        if left==0:\n",
    "            nums.remove(q)\n",
    "            flag = dfs(nums,str(q))  \n",
    "            return res[-1]\n",
    "        nums.remove(q+1)\n",
    "        flag = dfs(nums,str(q+1))\n",
    "        return res[-1]\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def getPermutation(self, n: int, k: int) -> str:\n",
    "        result = []\n",
    "\n",
    "        def dfs(current_depth, max_depth, path, list, is_used, start_index):\n",
    "            if len(result) >= k:\n",
    "                return\n",
    "            \n",
    "            if current_depth == max_depth + 1:\n",
    "                result.append(path.copy())\n",
    "                return\n",
    "\n",
    "            for index in range(len(list)):\n",
    "                if current_depth == 1 and index < start_index:\n",
    "                    continue\n",
    "                if is_used[index] is False:\n",
    "                    path.append(list[index])\n",
    "                    is_used[index] = True\n",
    "                    dfs(current_depth + 1, max_depth, path, list, is_used, start_index)\n",
    "                    is_used[index] = False\n",
    "                    path.pop()\n",
    "        list = []\n",
    "        for n_index in range(n):\n",
    "            list.append(n_index + 1)\n",
    "        max_depth = n\n",
    "        current_depth = 1\n",
    "        path = []\n",
    "        is_used = []\n",
    "        for _ in range(n):\n",
    "            is_used.append(False)\n",
    "        total_size = 1\n",
    "\n",
    "        for i in range(n - 1):\n",
    "            total_size *= (i + 1)\n",
    "        start_index = int(k / total_size) - 1\n",
    "        for i in range(total_size * start_index):\n",
    "            result.append([0])\n",
    "        dfs(current_depth, max_depth, path, list, is_used, start_index)\n",
    "        result_array = result[k - 1]\n",
    "\n",
    "        result_string = \"\"\n",
    "        for num in result_array:\n",
    "            result_string += str(num)\n",
    "        return result_string\n",
    "\n",
    "\n",
    "n = 3\n",
    "s = Solution()\n",
    "#print(3 - (int(3 / 2) * (2 * 1) + 1))\n",
    "#print(int(296662 / 40320))\n",
    "s.getPermutation(3, 3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import itertools\n",
    "class Solution:\n",
    "    def getPermutation(self, n: int, k: int) -> str:\n",
    "        return ''.join(list(itertools.permutations([str(x) for x in range(1, n+1)]))[k-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import itertools\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def getPermutation(self, n: int, k: int) -> str:\n",
    "        lis, lis2 = [], []\n",
    "        s = ''\n",
    "\n",
    "        for x in range(1, n + 1):\n",
    "            lis.append(str(x))\n",
    "\n",
    "        lis2 = list(itertools.permutations(lis))\n",
    "\n",
    "        for y in lis2[k - 1]:\n",
    "            s += y\n",
    "\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getPermutation(self, n: int, k: int) -> str:\n",
    "        return ''.join(str(_) for _ in list(permutations(list(range(1,n+1))))[k-1])"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
